package com.klun.project.common.constans.leetcode;

//给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。
// 示例 1：
//输入：root = [1,3,null,null,2]
//输出：[3,1,null,null,2]
//解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
// 示例 2：
//输入：root = [3,1,4,null,null,2]
//输出：[2,1,4,null,null,3]
//解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。
// 提示：
// 树上节点的数目在范围 [2, 1000] 内
// -231 <= Node.val <= 231 - 1
// 进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗？
// Related Topics 树 深度优先搜索 二叉搜索树 二叉树

import com.klun.project.common.constans.entity.TreeNode;
import com.klun.project.common.constans.utils.ParseUtils;

public class Solution99 {

	public void recoverTree(TreeNode root) {
		TreeNode x = null, y = null;
		TreeNode pred = null, predecessor = null;
		while (root != null) {
			if (root.left != null) {// 有左支
				predecessor = root.left;
				while (predecessor.right != null && predecessor.right != root) {
					predecessor = predecessor.right;
				}
				if (predecessor.right == null) {
					predecessor.right = root;
					root = root.left;
				} else {
					if (pred != null && root.val < pred.val) {
						y = root;
						if (x == null) {
							x = pred;
						}
					}
					pred = root;
					predecessor.right = null;
					root = root.right;
				}
			} else { // 无左支
				if (pred != null && root.val < pred.val) {
					y = root;
					if (x == null) {
						x = pred;
					}
				}
				pred = root;
				root = root.right;
			}
		}
		swap(x, y);
		System.out.println("a");
	}

	public void swap(TreeNode x, TreeNode y) {
		int tmp = x.val;
		x.val = y.val;
		y.val = tmp;
	}

	public static void main(String[] args) {
		Solution99 solution = new Solution99();
		TreeNode treeNode = ParseUtils.ArrayToBTree("[1,3,null,null,2]");
//		solution.recoverTree(treeNode);
		System.out.println(treeNode);
	}

}
